// 7.22 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。

// note:本题输出的是最短路径
#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\6Graph\2_Adjacency_Matrix\Adj_Matrix.h"
void fun_7_22(Adj_Matrix G, int i, int j) //从节点i到节点j的最短路径
{
    int stack[100];
    int top = -1;
    int visited[100] = {0};
    stack[++top] = i;
    visited[top] = 1;
    int w, n;
    w = -1;
    int shortest_path = INFINITY;
    int sp[100];
    while (top >= 0)
    {
        int p = stack[top];
        if (p == j)
        {
            if (top < shortest_path)
            {
                shortest_path = top;
                for (int k = 0; k <= top; k++)
                    sp[k] = stack[k];
            }
            // 直接输出路径

            // if (p == j)
            // {
            //     for (int s = 0; s <= top; s++)
            //         printf("%3d", sp[s]);
            // }
        }
        n = ++w;
        int flag = 0;
        while (n < G.node_num)
        {
            if (G.M[p][n] == 1 && visited[n] == 0)
            {
                flag = 1;
                stack[++top] = n;
                visited[top] = 1;
                w = -1;
                break;
            }
            n++;
        }
        if (!flag)
        {
            w = p;
            visited[top] = 0;
            top--;
        }
    }
    for (int s = 0; s <= shortest_path; s++)
        printf("%3d", sp[s]);
}

int main()
{
    /*******************code*******************/
    Adj_Matrix G;
    creat_G(G);
    fun_7_22(G, 0, 4);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
